package com.xjl.sort;

import com.xjl.utils.SortUtil;

/**
 * @描述： 荷兰国旗问题，给定一个整数数组，给定一个值K，
 *          这个值在原数组中一定存在，要求把数组中小于K的元素放到数组的左边，
 *          大于K的元素放到数组的右边，等于K的元素放到数组的中间，最终返回一个整数数组，
 *          其中只有两个值，分别是等于K的数组部分的左右两个下标值。
 * @作者： 许JIAN林
 */
public class Test03 {

    public static int[] partition(int[] arr, int num) {
        int less = -1;
        int more = arr.length;
        int cur = 0;
        while (cur < more) {
            if (arr[cur] < num){
                SortUtil.swap(arr, ++less, cur++);
            }else if (arr[cur] > num){
                SortUtil.swap(arr, --more, cur);
            }else{
                cur++;
            }
        }
        return new int[] {less + 1, more - 1 };
    }

    public static void main(String[] args) {
        int[] arr = {1,13,4,3,5,2,5,16};
        int[] partition = partition(arr, 5);
        SortUtil.display(arr);
        SortUtil.display(partition);

    }


}
